package Offer.offer2019;

import domain.ComplexListNode;

/**
 * 复杂链表的复制
 * @author: leiwenkang
 * @date: 2019/6/9
 * @time: 10:59
 */
public class Offer26 {
    /**
     * 分三步
     */
    public ComplexListNode cloneComplexListNode(ComplexListNode head) {
        if (head == null){
            return null;
        }
        //1.根据原来的链表的每个结点N，创建对应的N'，并将N'连接在N后面
        cloneNode(head);
        //2.设置副结点
        setSibling(head);
        //3.拆分新旧链表，返回新链表
        return getNewListNode(head);
    }


    private void cloneNode(ComplexListNode head) {
        ComplexListNode p = head;
        while (p != null) {
            ComplexListNode cloneNode = new ComplexListNode(p.val);
            cloneNode.next = p.next;
            p.next = cloneNode;
            p = cloneNode.next;
        }
    }


    private void setSibling(ComplexListNode head) {
        ComplexListNode p = head;
        while (p != null) {
            ComplexListNode cloneNode = p.next;
            if (p.sibling != null) {
                cloneNode.sibling = p.sibling.next;
            }

            p = cloneNode.next;
        }

    }

    private ComplexListNode getNewListNode(ComplexListNode head) {
        ComplexListNode newHead = head.next;

        ComplexListNode p = head;
        while (p != null) {
            ComplexListNode cloneNode = p.next;
            p.next = cloneNode.next;

            if (p.next != null) {
                cloneNode.next = cloneNode.next.next;
                p = p.next;
            }
        }

        return newHead;
    }

}
